/**
* Created with CLion.
* User:Lenovo
* Date:2023-05-30
* Time:22:31
* Description:树的相关概念
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Heap/Heap.h"

// 结点的度：一个结点含有的子树
// 叶结点或终端结点：度为 0 的结点
// 非终端结点或分支结点：度不为 0 的结点
// 根结点：没有前驱结点(父结点)，也是分支结点
// 双亲结点或父结点：含有子结点的结点
// 孩子结点或子结点：一个节点含有的子树的根结点
// 兄弟结点：具有相同父结点的结点(亲兄弟)
// 树的度：一棵树中最大的结点的度
// 结点的层次：从根开始定义起，根为第一层，根的子结点为第二层
// 树的高度或深度：树中结点的最大层次
    // 空树的高度可以是 0 / -1，只有根节点的树的高度可以是 1 / 0
// 堂兄弟结点：双亲在同一层的结点
// 结点的祖先：从根到该结点所经分支上的所有结点
// 子孙：以某结点为根的子树中的任意结点
// 森林：由 m 棵互不相交的树的集合

// 树由两部分构成：父(根)结点和 N 棵子树 - 递归结构 -> 重点用递归
// 子树之间不能相交，否则就不是树 -> 图

// 树的定义

struct TreeNode1
{
    int data;
    struct TreeNode *child1;
    struct TreeNode *child2;
    // ...
};
// 1.如果明确了树的度，那么可以定义
// 2.顺序表存储孩子
// 3.双亲表示法：每个位置只存储双亲的指针或下标
// 4.左孩子右兄弟表示法：简化了树的结构定义

struct TreeNode2
{
    struct TreeNode2 *firstChild1;// 第一个孩子结点
    struct TreeNode2 *pNextBrother;// 指向其下一个兄弟结点
    int data;// 结点中的数据域
};

//            A ->
//           /
//          B - C - D ->
//         /     \
//        E - F   G ->
//       /       /
//      J       K - L ->

// 应用：Linux 文件系统：一棵目录树
// Windows 文件系统：森林 -> C D E 盘

// 二叉树
    // 所有节点的度最大为 2
    // 孩子：分为左孩子和右孩子
    // 满二叉树：每一层都是满的，如果高度为 h，结点的数量就是 2 ^ h - 1，第 i 层有 2 ^ (i - 1) 个结点
    // 完全二叉树：高度是 h，前 h - 1 层都是满的，最后一层可以不满，但是从左到右是连续的，结点范围 [2 ^ (h - 1)，2 ^ h - 1]
    // 用数组存储二叉树：父子间的下标关系
        // 父亲 -> 左孩子：leftChild = parent * 2 + 1
        // 父亲 -> 右孩子：rightChild = parent * 2 + 2
        // 孩子 -> 父亲：parent = (child - 1) / 2
        // 只有完全二叉树才适合用数组存储，否则会造成大量的空间浪费

// 堆：逻辑结构(想象出来的)是完全二叉树 - 物理结构(真实存在的)是一个数组
// 分为大堆和小堆
// 大根堆：树的任何一个父亲都大于等于孩子
// 小根堆：树的任何一个父亲都小于等于孩子
// 应用：堆排序 O(N*logN)，topK，优先队列
// topK：求 N 个数中最大的前 K 个 -> 大根堆 - 优质筛选问题
    // 当 topK 问题的数据量过大的时候，正常思路，即建大堆再 Pop 是不可能实现的
    // 因为数据量太大，存放在磁盘当中，无法随机访问
    // 思路：建 K 个数的小堆，后面 N - K 个数依次比较，如果比堆顶的数据大，就替换他进堆(覆盖堆顶值，向下调整)
    // 最后这个小堆的值就是最大的前 K 个
    // 时间复杂度 O((N - K) * logK)

// 性质：对任何一棵二叉树，如果度为 0 的叶子结点个数为 n0，度为 2 的分支结点个数为 n2，那么 n0 = n2 + 1

void CreateNDate()
{
    int n = 1000000;
    srand(time(0));
    const char *file = "data.txt";
    FILE *fin = fopen(file, "w");
    if (fin == NULL)
    {
        perror("fopen error");
        return;
    }

    for (size_t i = 0; i < n; i++)
    {
        int x = rand() % 1000000;
        fprintf(fin, "%d\n", x);
    }

    fclose(fin);
}

void PrintTopK(int k)
{
    srand(time(0));
    const char *file = "data.txt";
    FILE *fout = fopen(file, "r");
    if (fout == NULL)
    {
        perror("malloc error");
        return;
    }

    int *kminHeap = (int *)malloc(sizeof(int) * k);
    if (kminHeap == NULL)
    {
        perror("malloc error");
        return;
    }

    for (int i = 0; i < k; i++)
    {
        fscanf(fout, "%d", kminHeap + i);
    }

    // 建小堆
    for (int i = (k - 2) / 2; i >= 0; i--)
    {
        AdjustDown(kminHeap, k, i);
    }

    int val = 0;
    while (!feof(fout))
    {
        fscanf(fout, "%d", &val);
        if (val > kminHeap[0])
        {
            kminHeap[0] = val;
            AdjustDown(kminHeap, k, 0);
        }
    }

    for (int i = 0; i < k; i++)
    {
        printf("%d ", kminHeap[i]);
    }
}

int main()
{
    CreateNDate();
    PrintTopK(5);

    return 0;
}
